package com.fe.class01;

import java.util.Arrays;

/**
 * @Description Code03_InsertionSort
 * @Author sosuke :-)
 * @Date 2021/11/30 22:22
 */
public class Code03_InsertionSort {
    /**
     * 想让arr[0~0]上有序，这个范围只有一个数，当然是有序的。
     * 想让arr[0~i]上有序，所以从arr[i]开始往前看，arr[i]这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动
     * 最差情况下，每一步常数操作的数量，和等差数列一般，所以O(N^2)
     * @param arr
     */
    public static void insertionSort(int[] arr) {
        // 数组至少有两个数
        if (null == arr || arr.length < 2) return;
        // 保证0～i有序，i = 0时，只有一个数，有序；i = 1时，向左看
        for (int i = 1; i < arr.length; i++) {
            // 逆向比较
            // for (int j = i; j > 0; j--) {
            //     if (arr[j] < arr[j - 1]) {
            //         swap(arr, j, j - 1);
            //     }
            // }

            // 正向比较
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(arr, j, j + 1);
            }
        }
    }

    private static void swap(int[] arr, int j, int i) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

    /**
     * 测试次数
     * 数组数据个数
     * 数组中最大值
     * @param args
     */
    public static void main(String[] args) {
        int testTime = 500000; // 测试次数
        int maxSize = 100; // 数组数据个数
        int maxValue = 100; // 数组中最大值
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = Arrays.copyOf(arr1, arr1.length);
            insertionSort(arr1);
            Arrays.sort(arr2);
            if (!Arrays.equals(arr1, arr2)) {
                succeed = false;
                System.out.println(Arrays.toString(arr1));
                System.out.println(Arrays.toString(arr2));
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");

        int[] arr = generateRandomArray(maxSize, maxValue);
        System.out.println(Arrays.toString(arr));
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize+1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random() - maxSize * Math.random());
        }
        return arr;
    }
}
